Stack

Introduction#

The stack is a data structure that operates on the last-in-first-out (LIFO) principle. This means that the elements that we inserted last would be removed first.

Applications of stacks#

The stack is used in a wide variety of applications, including:

• Implementation of recursive calls.
• Postfix evaluation of an expression.
• Backtracking.
• Depth-first search of trees and graphs.
• Converting a decimal to a binary number, and so on.

Stack ADT Operations#

• Push(k) pushes a value k to the top of the stack.
• Pop() removes an element from the top of the stack and return its value.
• Top() returns the value of the element on top of the stack.
• Size() returns the number of elements in the stack.
• IsEmpty() tells us whether the stack is empty or not. If the stack is empty, it returns true. Otherwise, it returns false.

Note: All of the above operations are implemented in $O(1)$ time complexity.

To see how stacks work, let’s look at the illustration below:

Example#

Stack is implemented in Go as follows:

We’ll learn about stacks in detail in a later chapter.